public class MyTree {
    public class Tree{
        public char val;
        private Tree left;
        private Tree right;
        public Tree(char val) {
            this.val = val;
        }
    }
    //以穷举的方式 创建一棵二叉树出来
    public Tree createTree() {
        Tree A = new Tree('A');
        Tree B = new Tree('B');
        Tree C = new Tree('C');
        Tree D = new Tree('D');
        Tree E = new Tree('E');
        Tree F = new Tree('F');
        Tree G = new Tree('G');
        Tree H = new Tree('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        E.right = H;
        C.left = F;
        C.right = G;
        return A;
    }

    //前序遍历  根-左子树-右子树
    public void preOrder(Tree tree) {
        if (tree == null) {
            return;
        }
        System.out.print(tree.val + " ");
        preOrder(tree.left);
        preOrder(tree.right);
    }

    //中序遍历  左子树-根-右子树
    public void inOrder(Tree tree) {
        if (tree == null) {
            return;
        }
        inOrder(tree.left);
        System.out.print(tree.val + " ");
        inOrder(tree.right);
    }
    //后序遍历 左子树-右子树-根
    public void postOrder(Tree tree) {
        if (tree == null) {
            return;
        }
        postOrder(tree.left);
        postOrder(tree.right);
        System.out.print(tree.val + " ");
    }
    //获得 节点个数
    public int size(Tree tree) {
        if (tree == null) {//当没有节点时返回0
            return 0;
        }
        //当此时节点 左右都为null 则返回1
        return size(tree.left) + size(tree.right) + 1;
    }
    //获得 叶子节点的个数
    public int getLeafNodeCount(Tree tree) {
        if (tree == null) {//本身为空 返回0 不然下面会调用null
            return 0;
        }
        if (tree.left == null && tree.right == null) {//判断是否是叶子节点
            return 1;
        }
        return getLeafNodeCount(tree.left) +
                getLeafNodeCount(tree.right);

    }
    //获得 第k层 节点的个数
    public int getLeafNodeCount(Tree tree , int k) {
        if (tree == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return getLeafNodeCount(tree.left , k-1) +
                getLeafNodeCount(tree.right , k-1);

    }
    // 获取二叉树的高度
    public int getHeight(Tree tree) {
        if (tree == null) {
            return 0;
        }
        int left = getHeight(tree.left);
        int right = getHeight(tree.right);

        return (left > right ? left : right) + 1;
    }
    // 检测值为value的元素是否存在
    public Tree find(Tree tree , char val) {
        if (tree == null) {
            return null;
        }
        if (tree.val == val) {
            return tree;
        }
        Tree cmp = find(tree.left , val);
        if (cmp != null) {
            return cmp;
        }
        cmp = find(tree.right , val);
        if (cmp != null) {
            return cmp;
        }
        return null;
    }
}
